{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #K-Similar Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kSimilarity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #相似度为 K 的字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>对于某些非负整数 <code>k</code> ，如果交换 <code>s1</code> 中两个字母的位置恰好 <code>k</code> 次，能够使结果字符串等于 <code>s2</code> ，则认为字符串 <code>s1</code> 和 <code>s2</code> 的<strong> 相似度为 </strong><code>k</code><strong> </strong><strong>。</strong></p>\n",
    "\n",
    "<p>给你两个字母异位词 <code>s1</code> 和 <code>s2</code> ，返回 <code>s1</code> 和 <code>s2</code> 的相似度 <code>k</code><strong> </strong>的最小值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"ab\", s2 = \"ba\"\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s1 = \"abc\", s2 = \"bca\"\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s1.length &lt;= 20</code></li>\n",
    "\t<li><code>s2.length == s1.length</code></li>\n",
    "\t<li><code>s1</code>&nbsp;和&nbsp;<code>s2</code>&nbsp;&nbsp;只包含集合&nbsp;<code>{'a', 'b', 'c', 'd', 'e', 'f'}</code>&nbsp;中的小写字母</li>\n",
    "\t<li><code>s2</code> 是 <code>s1</code> 的一个字母异位词</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [k-similar-strings](https://leetcode.cn/problems/k-similar-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [k-similar-strings](https://leetcode.cn/problems/k-similar-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ab\"\\n\"ba\"', '\"abc\"\\n\"bca\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "        n, ls1, self.ans = len(s1), list(s1), 20\n",
    "        def dfs(idx, cnt):\n",
    "            if idx == n: self.ans = min(self.ans, cnt)\n",
    "            elif ls1[idx] == s2[idx]: dfs(idx + 1, cnt)\n",
    "            else:\n",
    "                for nexti in range(idx + 1, n):\n",
    "                    if s2[idx] == ls1[nexti] != s2[nexti]:\n",
    "                        ls1[nexti] = ls1[idx]\n",
    "                        ls1[idx] = s2[idx]\n",
    "                        dfs(idx + 1, cnt + 1)\n",
    "                        ls1[idx] = ls1[nexti]\n",
    "                        ls1[nexti] = s2[idx]\n",
    "        dfs(0, 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "class Solution:\r\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\r\n",
    "        s,t=[],[]\r\n",
    "        for x,y in zip(s1,s2):\r\n",
    "            if x!=y:\r\n",
    "                s.append(x)\r\n",
    "                t.append(y)\r\n",
    "        n=len(s)\r\n",
    "        if n==0:\r\n",
    "            return 0\r\n",
    "        ret=n-1\r\n",
    "        def dfs(idx,cost):\r\n",
    "            nonlocal n,ret\r\n",
    "            if cost>ret:\r\n",
    "                return\r\n",
    "            while idx<n and s[idx]==t[idx]:\r\n",
    "                idx+=1\r\n",
    "            if idx==n:\r\n",
    "                ret=cost\r\n",
    "                return\r\n",
    "            diff=sum(s[i]!=t[i] for i in range(idx,n))\r\n",
    "            min_cost=cost+(diff+1)//2\r\n",
    "            if min_cost>=ret:\r\n",
    "                return\r\n",
    "            for j in range(idx+1,n):\r\n",
    "                if s[j]==t[idx]:\r\n",
    "                    s[j],s[idx]=s[idx],s[j]\r\n",
    "                    dfs(idx+1,cost+1)\r\n",
    "                    s[j],s[idx]=s[idx],s[j]\r\n",
    "\r\n",
    "        dfs(0,0)\r\n",
    "        return ret\r\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "        s, t = [], []\n",
    "        for x, y in zip(s1, s2):\n",
    "            if x != y:\n",
    "                s.append(x)\n",
    "                t.append(y)\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "\n",
    "        ans = n - 1\n",
    "        def dfs(i: int, cost: int) -> None:\n",
    "            nonlocal ans\n",
    "            if cost > ans:\n",
    "                return\n",
    "            while i < n and s[i] == t[i]:\n",
    "                i += 1\n",
    "            if i == n:\n",
    "                ans = min(ans, cost)\n",
    "                return\n",
    "            diff = sum(s[j] != t[j] for j in range(i, len(s)))\n",
    "            min_swap = (diff + 1) // 2\n",
    "            if cost + min_swap >= ans:  # 当前状态的交换次数下限大于等于当前的最小交换次数\n",
    "                return\n",
    "            for j in range(i + 1, n):\n",
    "                if s[j] == t[i]:\n",
    "                    s[i], s[j] = s[j], s[i]\n",
    "                    dfs(i + 1, cost + 1)\n",
    "                    s[i], s[j] = s[j], s[i]\n",
    "        dfs(0, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "        from_s1 = dict()\n",
    "        n = len(s1)\n",
    "\n",
    "        def dis(s1, s2):\n",
    "            cnt = 0\n",
    "            for x, y in zip(s1, s2):\n",
    "                cnt += x != y\n",
    "              \n",
    "            return cnt // 2\n",
    "\n",
    "        from_s1[s1] = 0\n",
    "        q = [(0, s1)]\n",
    "\n",
    "        while q:\n",
    "            _, s = heapq.heappop(q)\n",
    "            if s == s2:\n",
    "                return from_s1[s2]\n",
    "\n",
    "            i = 0\n",
    "            while s[i] == s2[i]:\n",
    "                i += 1    \n",
    "\n",
    "            for j in range(i+1, n):\n",
    "                if s[j] == s2[i]:\n",
    "                    s_new = list(s)\n",
    "                    s_new[i], s_new[j] = s_new[j], s_new[i]\n",
    "                    s_new = ''.join(s_new)\n",
    "                    if s_new not in from_s1 or from_s1[s] + 1 < from_s1[s_new]: \n",
    "                        d = dis(s_new, s2)\n",
    "                        heapq.heappush(q, (from_s1[s] + 1 + d, s_new))\n",
    "                        from_s1[s_new] = from_s1[s] + 1\n",
    "\n",
    "        return -1\n",
    "\n",
    "                                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "        n = len(s1)\n",
    "        def next(s):\n",
    "            i = 0\n",
    "            while s[i] == s2[i]:\n",
    "                i += 1\n",
    "            return [s[:i] + s[j] + s[i+1:j] + s[i] + s[j+1:] for j in range(i+1, n) if s[j] == s2[i] and s[j] != s2[j]]\n",
    "        q = [s1]\n",
    "        vis = {s1}\n",
    "        ans = 0\n",
    "        while len(q) > 0:\n",
    "            p = q\n",
    "            q = []\n",
    "            for node in p:\n",
    "                if node == s2:\n",
    "                    return ans\n",
    "                for nxt in next(node):\n",
    "                    if nxt not in vis:\n",
    "                        vis.add(nxt)\n",
    "                        q.append(nxt)\n",
    "            ans += 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "        def next(s):\n",
    "            i = 0\n",
    "            while s[i] == s2[i]:\n",
    "                i += 1\n",
    "            res = []\n",
    "            for j in range(i + 1, n):\n",
    "                if s[j] == s2[i] and s[j] != s2[j]:\n",
    "                    res.append(s2[: i + 1] + s[i + 1 : j] + s[i] + s[j + 1 :])\n",
    "            return res\n",
    "\n",
    "        q = deque([s1])\n",
    "        vis = {s1}\n",
    "        ans, n = 0, len(s1)\n",
    "        while 1:\n",
    "            for _ in range(len(q)):\n",
    "                s = q.popleft()\n",
    "                if s == s2:\n",
    "                    return ans\n",
    "                for nxt in next(s):\n",
    "                    if nxt not in vis:\n",
    "                        vis.add(nxt)\n",
    "                        q.append(nxt)\n",
    "            ans += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "        step, n = 0, len(s1)\n",
    "        q, vis = [(s1, 0)], {s1}\n",
    "        while True:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for s,i in tmp:\n",
    "                if s == s2:\n",
    "                    return step\n",
    "                while i < n and s[i] == s2[i]:\n",
    "                    i += 1\n",
    "                for j in range(i+1, n):\n",
    "                    if s[j] == s2[i] != s2[j]:\n",
    "                        t = list(s)\n",
    "                        t[i], t[j] = t[j], t[i]\n",
    "                        t = ''.join(t)\n",
    "                        if t not in vis:\n",
    "                            vis.add(t)\n",
    "                            q.append((t, i+1))\n",
    "            step += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "        step, n = 0, len(s1)\n",
    "        q, vis = [(s1, 0)], {s1}\n",
    "        while True:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for s, i in tmp:\n",
    "                if s == s2:\n",
    "                    return step\n",
    "                while i < n and s[i] == s2[i]:\n",
    "                    i += 1\n",
    "                for j in range(i+1, n):\n",
    "                    if s[j] == s2[i] != s2[j]:\n",
    "                        t = list(s)\n",
    "                        t[i], t[j] = t[j], t[i]\n",
    "                        t = ''.join(t)\n",
    "                        if t not in vis:\n",
    "                            vis.add(t)\n",
    "                            q.append((t, i+1))\n",
    "            step += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "        step, n = 0, len(s1)\n",
    "        q, vis = [(s1, 0)], {s1}\n",
    "        while True:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for s, i in tmp:\n",
    "                if s == s2:\n",
    "                    return step\n",
    "                while i < n and s[i] == s2[i]:\n",
    "                    i += 1\n",
    "                for j in range(i + 1, n):\n",
    "                    if s[j] == s2[i] != s2[j]:  # 剪枝，只在 s[j] != s2[j] 时去交换\n",
    "                        t = list(s)\n",
    "                        t[i], t[j] = t[j], t[i]\n",
    "                        t = ''.join(t)\n",
    "                        if t not in vis:\n",
    "                            vis.add(t)\n",
    "                            q.append((t, i + 1))\n",
    "            step += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "        step, n = 0, len(s1)\n",
    "        q, vis = [(s1, 0)], {s1}\n",
    "        while True:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for s, i in tmp:\n",
    "                if s == s2:\n",
    "                    return step\n",
    "                while i < n and s[i] == s2[i]:\n",
    "                    i += 1\n",
    "                for j in range(i + 1, n):\n",
    "                    if s[j] == s2[i] != s2[j]:  # 剪枝，只在 s[j] != s2[j] 时去交换\n",
    "                        t = list(s)\n",
    "                        t[i], t[j] = t[j], t[i]\n",
    "                        t = ''.join(t)\n",
    "                        if t not in vis:\n",
    "                            vis.add(t)\n",
    "                            q.append((t, i + 1))\n",
    "            step += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "        step, n = 0, len(s1)\n",
    "        q, vis = [(s1, 0)], {s1}\n",
    "        while True:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for s, i in tmp:\n",
    "                if s == s2:\n",
    "                    return step\n",
    "                while i < n and s[i] == s2[i]:\n",
    "                    i += 1\n",
    "                for j in range(i + 1, n):\n",
    "                    if s[j] == s2[i] != s2[j]:  # 剪枝，只在 s[j] != s2[j] 时去交换\n",
    "                        t = list(s)\n",
    "                        t[i], t[j] = t[j], t[i]\n",
    "                        t = ''.join(t)\n",
    "                        if t not in vis:\n",
    "                            vis.add(t)\n",
    "                            q.append((t, i + 1))\n",
    "            step += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "        step, n = 0, len(s1)\n",
    "        q, vis = [(s1, 0)], {s1}\n",
    "        while True:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for s, i in tmp:\n",
    "                if s == s2:\n",
    "                    return step\n",
    "                while i < n and s[i] == s2[i]:\n",
    "                    i += 1\n",
    "                for j in range(i + 1, n):\n",
    "                    if s[j] == s2[i] != s2[j]:  # 剪枝，只在 s[j] != s2[j] 时去交换\n",
    "                        t = list(s)\n",
    "                        t[i], t[j] = t[j], t[i]\n",
    "                        t = ''.join(t)\n",
    "                        if t not in vis:\n",
    "                            vis.add(t)\n",
    "                            q.append((t, i + 1))\n",
    "            step += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "        step, n = 0, len(s1)\n",
    "        q, vis = [(s1, 0)], {s1}\n",
    "        while True:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for s, i in tmp:\n",
    "                if s == s2:\n",
    "                    return step\n",
    "                while i < n and s[i] == s2[i]:\n",
    "                    i += 1\n",
    "                for j in range(i+1, n):\n",
    "                    if s[j] == s2[i] != s2[j]:\n",
    "                        t = list(s)\n",
    "                        t[i], t[j] = t[j], t[i]\n",
    "                        t = ''.join(t)\n",
    "                        if t not in vis:\n",
    "                            vis.add(t)\n",
    "                            q.append((t, i+1))\n",
    "            step += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "\n",
    "        queue = collections.deque([(s1, 0)])\n",
    "        seen = set()\n",
    "        seen.add(s1)\n",
    "\n",
    "        while queue:\n",
    "            node, step = queue.popleft()\n",
    "\n",
    "            if node == s2:\n",
    "                return step\n",
    "\n",
    "            ss = list(node)\n",
    "\n",
    "            i = 0\n",
    "\n",
    "            while i < len(ss) and ss[i] == s2[i]:\n",
    "                i += 1\n",
    "            # i处不相等\n",
    "            \n",
    "            k = i + 1\n",
    "\n",
    "            while k < len(ss):\n",
    "                if ss[k] == s2[i] and ss[k] != s2[k]:\n",
    "                    ss[k], ss[i] = ss[i], ss[k]\n",
    "                    new = ''.join(ss)\n",
    "\n",
    "                    if new not in seen:\n",
    "                        seen.add(new)\n",
    "                        queue.append((new, step + 1))\n",
    "                    ss[k], ss[i] = ss[i], ss[k]\n",
    "                    \n",
    "                k += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "        step, n = 0, len(s1)\n",
    "        q, vis = [(s1, 0)], {s1}\n",
    "        while True:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for s, i in tmp:\n",
    "                if s == s2:\n",
    "                    return step\n",
    "                while i < n and s[i] == s2[i]:\n",
    "                    i += 1\n",
    "                for j in range(i+1, n):\n",
    "                    if s[j] == s2[i] != s2[j]:\n",
    "                        t = list(s)\n",
    "                        t[i], t[j] = t[j], t[i]\n",
    "                        t = ''.join(t)\n",
    "                        if t not in vis:\n",
    "                            vis.add(t)\n",
    "                            q.append((t, i+1))\n",
    "            step += 1\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "        step, n = 0, len(s1)\n",
    "        q, vis = [(s1, 0)], {s1}\n",
    "        while True:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for s, i in tmp:\n",
    "                if s == s2:\n",
    "                    return step\n",
    "                while i < n and s[i] == s2[i]:\n",
    "                    i += 1\n",
    "                for j in range(i + 1, n):\n",
    "                    if s[j] == s2[i] and s[j] != s2[j]:\n",
    "                        t = list(s)\n",
    "                        t[i], t[j] = t[j], t[i]\n",
    "                        t = ''.join(t)\n",
    "                        if t not in vis:\n",
    "                            vis.add(t)\n",
    "                            q.append((t, i + 1))\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "        step, n = 0, len(s1)\n",
    "        q, vis = [(s1, 0)], {s1}\n",
    "        while True:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for s, i in tmp:\n",
    "                if s == s2:\n",
    "                    return step\n",
    "                while i < n and s[i] == s2[i]:\n",
    "                    i += 1\n",
    "                for j in range(i+1, n):\n",
    "                    if s[j] == s2[i] != s2[j]:\n",
    "                        t = list(s)\n",
    "                        t[i], t[j] = t[j], t[i]\n",
    "                        t = ''.join(t)\n",
    "                        if t not in vis:\n",
    "                            vis.add(t)\n",
    "                            q.append((t, i))\n",
    "\n",
    "            step += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kSimilarity(self, A: str, B: str) -> int:\n",
    "        def nei(s):\n",
    "            i = 0\n",
    "            while s[i] == B[i]:\n",
    "                i += 1\n",
    "            for j in range(i+1, len(s)):\n",
    "                if s[j] == B[i]:\n",
    "                    yield s[:i] + s[j] + s[i+1:j] + s[i] + s[j+1:]\n",
    "\n",
    "        queue = [(A, 0)]\n",
    "        seen = {A}\n",
    "        while queue:\n",
    "            s, swaps = queue.pop(0)\n",
    "            if s == B:\n",
    "                return swaps\n",
    "            for t in nei(s):\n",
    "                if t not in seen:\n",
    "                    seen.add(t)\n",
    "                    queue.append((t, swaps+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def kSimilarity(self, s1: str, s2: str) -> int:\n",
    "        # print(s1,s2)\n",
    "        if s1 == s2:\n",
    "            return 0\n",
    "        n = len(s1)\n",
    "        ret = n-1\n",
    "        # print(ret)\n",
    "        for i in range(n):\n",
    "            if s1[i] == s2[i]:\n",
    "                continue\n",
    "            for j in range(i+1,n):\n",
    "                if s1[j] == s2[j]:\n",
    "                    continue\n",
    "                if s2[j] != s1[i]:\n",
    "                    continue\n",
    "                # print(s1,i,ret)\n",
    "                ret = min(ret, self.kSimilarity(s1[i+1:], s2[i+1:j]+s2[i]+s2[j+1:])+1)\n",
    "                # print(2,s1,i,j,ret)\n",
    "            break\n",
    "        # print(s1,s2,ret)\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
